//416 数组分割
/*
给定一个正整数数组，求是否可以把这个数组分成和相等的两部分
等价于 0-1 背包问题

输入输出样例：
	输入是一个一维正整数数组，输出时一个布尔值，表示是否可以满足题目要求

Input: [1,5,11,5]
Output: true

*/
bool canPartition(vector<int> &nums)
{
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2)
		return false;
	int target = sum / 2, n = nums.size();
	vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
	for (int i = 0; i <= n; ++i)
	{
		dp[i][0] = true;
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = nums[i - 1]; j <= target; ++j)
		{
			dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
		}
	}
	return dp[n][target];
}
//空间优化
bool canPartition(vector<int> &nums)
{
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum % 2)
		return false;
	int target = sum / 2, n = nums.size();
	vector<bool> dp(target + 1, false);
	dp[0] = true;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = target; j >= nums[i - 1]; --j)
		{
			dp[j] = dp[j] || dp[j - nums[i - 1]];
		}
	}
	return dp[target];
}